#!/usr/bin/env python

"""
Copyright 2010 Jay Young

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

Author: Jay Young (jayyoung9909@gmail.com)
"""

import re
import os
import sys
import json
import logging

# Terms:
#
# Because there are two different dependency graphs at work, the module
# dependency graph and the namespace dependency graph, the following terms are
# used consistently to avoid confusion between the two:
#
# "nDependent" - A namespace that is dependent upon the namespace in question
# Ex: goog.dom is an nDependent of goog.string
#
# "nDependency" - A namespace upon which the namespace in question is dependent
# Ex: goog.string is an nDependency of goog.dom
#
# "mDependent" - A module that is dependent upon the module in question
# Ex: If the "app_core" module must be loaded for the "settings" module to
# function, then "settings" is an mDependent of "app_core"
#
# "mDependency" - A module upon which the module in question is dependent
# Ex: If the "app_core" module must be loaded for the "settings" module to
# function, then the "app_core" module is an mDependency of "settings"


class ModuleBuilder(object):
  """Automatically compiles your project into user-defined modules.
  
  The ModuleBuilder class is responsible for parsing the module and namespace
  dependencies in your project and passing your code to the Closure Compiler
  so as to generate user-defined modules.
  
  For readability, the term "modules.js" is used to refer to the file passed
  in to the ModuleBuilder instance that defines the modules structure.
  
  Args:
    modules_file_name: The name of the file that defines your project's modules.
    
  Attributes:
    init_level: How far along the ModuleBuilder instance is towards its full
        initialization.
    modules: A list of module objects parsed from the given modules.js file
        The module objects in the list will accumulate most of the key
        information required to perform the script's actions.
        Defined in: `parse_modules()`
    n_dependency_map: A map of all namespaces to their nDependencies.
        Defined in: `map_namespace_dependencies()`
    namespace_filenames: A map of namespaces to the files in which they're
        defined.
        Defined in: `map_namespace_dependencies()`
    namespaces_to_module_map: A map of namespaces to the names of all modules
        in which they are required.
        Defined in: map_module_namespaces()`
    modules_map: A map of module names to their defining object in `modules`
  """
  
  class InitLevel(object):
    """Enum to describe the current loading stage of the ModuleBuilder instance
    
    The ModuleBuilder instance can be progressively initialized, so the class
    members of this represent the possible incremental states:
    
    Attributes:
      UNINITIALIZED: The object has been constructed but done no processing.
      PARSED_MODULES: The given file describing the modules has been parsed.
      M_DEPENDENCIES_MARKED: The mDependency tree has been built.
      N_DEPENDENCIES_MARKED: The nDependency tree has been built.
      MODULE_NAMESPACES_MAPPED: Namespaces have been mapped to the modules that
          use them.
      DEPENDENCIES_PLACED: Namespaces have been placed in the modules that most
          make sense.
    """
    UNINITIALIZED = 0
    PARSED_MODULES = 1
    M_DEPENDENCIES_MARKED = 2
    N_DEPENDENCIES_MAPPED = 3
    MODULE_NAMESPACES_MAPPED = 4
    DEPENDENCIES_PLACED = 5

  def __init__(self, modules_file_name=u'modules.js'):
    """Set up the ModuleBuilder instance state"""
    
    self.modules_file_name = modules_file_name
    self.init_level = ModuleBuilder.InitLevel.UNINITIALIZED

  def parse_modules(self):
    """Read and parse the module config file passed to __init__
    
    `parse_modules()` builds the ModuleBuilder.modules list from the given
    configuration file.  This module objects in the list contains:
      'name':  Name of the module being described
      'mDepdendencies': The modules on which this module is dependent
      'namespaces': The user-defined namespaces in this module
      
    Defines:
      self.modules
      
    TODO:
      Instead of taking input from a modules config file, decide if we want to
      parse the source directly for some module-declaring primitives.
    """
    
    logging.info("Parsing %s file..." % self.modules_file_name)
    
    modules_file = open(self.modules_file_name, 'r')
    
    # The first line is filler to allow the file to validate as javascript
    # Read the first line, strip the trailing newline, and get just the '['
    modules = modules_file.readline().strip()[-1:]
    modules = ("%s%s" % (modules, ''.join([line.strip()
                                      for line in modules_file.readlines()])))
    
    modules_file.close()
    
    if modules[-1] == ';':
      self.modules = json.loads(modules[:-1])
    else:
      self.modules = json.loads(modules)
    
    # Create a map of module names to module objects to prevent repeated array
    # traversals.
    self.modules_map = {}
    
    for module in self.modules:
      self.modules_map[module["name"]] = module
    
    self.init_level = ModuleBuilder.InitLevel.PARSED_MODULES
  
  def mark_dependency(self, module_name, dependencies, level):
    """Mark out a module's dependency path.
    
    Helper method for mark_module_dependencies that recursively traverses the
    mDependency tree.  This method adds an array to each module
    in the self.modules array containsing a list of mDependents
    and how many levels up their mDependency tree this module is.
    
    Args:
      module_name: The module whose mDependency tree is being traversed.
      dependencies: The mDependencies array in the module dict from modules.js
      level: Current depth into the mDependency tree
    """
    
    for dependency in dependencies:
      
      m_dependency = self.modules_map[dependency]
      if "m_dependents" not in m_dependency:
        m_dependency["m_dependents"] = []
      
      m_dependent = {
        "dependent_name": module_name,
        "level": level
      }
      
      m_dependency["m_dependents"].append(m_dependent)
      self.mark_dependency(module_name,
                           m_dependency["mDependencies"], level + 1)
  
  def mark_module_dependencies(self):
    """Traverse modules array to mark module dependents.
    
    Iterates through the modules array to mark out mDependency paths.
    See mark_dependency for further documentation.
    """
    
    if self.init_level != ModuleBuilder.InitLevel.PARSED_MODULES:
      self.parse_modules()
    
    logging.info("Marking module dependencies...")
    
    # For each module, traverse its dependencies and mark them.
    for module in self.modules:
      self.mark_dependency(module["name"], module["mDependencies"], 1)
    
    self.init_level = ModuleBuilder.InitLevel.M_DEPENDENCIES_MARKED
  
  def load_deps_file(self, filename, root_path, pattern):
    """Parse a dependency file into a namespace dependency map.
    
    Helper method for map_namespace_dependencies.
    Read in a dependency file created using depswriter.py, parse the
    dependencies, and append them to the given dict.  This is split into its
    own method so we can use the given deps.js file for the Closure library and
    only have to run depswriter.py on user-defined code.
    
    Args:
      filename: The name (including path) of the deps file to parse.
      root_path: The path to append to the beginning of the file name.
      pattern: The RegExp pattern.  Passed in to prevent multiple compilations.
    """
    
    # Open the deps file and parse it.
    deps_file = open(filename)
    for dep in deps_file:
      # Strip whitespace and convert any single quotes to double quotes to
      # allow the array strings to be easily parsed via JSON.loads()
      dep = dep.strip().replace(r"'", r'"')
      
      matches = pattern.match(dep)
      
      # The first two lines of the file should fail, since those are the
      # "autogenerated, do not delete" comments.
      if matches != None:
        ns_filename = matches.group('filename') # File name string
        provided = json.loads(matches.group('provided')) # Provided namespaces
        required = json.loads(matches.group('required')) # Required namespaces
        
        ns_filename = ns_filename.strip('"').strip("'")
        ns_filename = os.path.join(root_path, ns_filename)
        ns_filename = os.path.normpath(ns_filename)
        
        self.filenames_to_namespaces[ns_filename] = provided
        
        for namespace in provided:
          self.namespace_filenames[namespace] = ns_filename
          self.n_dependency_map[namespace] = required
    
    deps_file.close()

  def map_namespace_dependencies(self):
    """Maps namespaces to their dependencies, both goog.* and user-defined.
    
    Uses the depswriter.py utility to build the dependency file for goog.* and
    user-defined namespaces, then parses to build a map of all namespaces to
    their nDependencies.
    
    Defines:
      self.n_dependency_map
      self.namespace_filenames
      self.filenames_to_namespaces
      
    TODO:
      Change path assumptions to accept command-line argument.
      Update method to interface with the other tools directly instead of
          executing depswriter.py and parsing output.
      Instead of hard-coding the three deps files (Closure Lib, third party,
          and app deps files), set up to alllow a variable number.
    """
    
    if self.init_level != ModuleBuilder.InitLevel.M_DEPENDENCIES_MARKED:
      self.mark_module_dependencies()
    
    logging.info("Building namespace dependency list...")
    
    # For now, all paths assume that the Closure library and tools were
    # checked out with the command shown at:
    #   http://code.google.com/p/closure-library/source/checkout
    
    DEPSWRITER = "../closure-library-read-only/closure/bin/build/depswriter.py"
    
    CLOSURE_PATH = "../closure-library-read-only/closure/goog/"
    CLOSURE_DEPS = "%s%s" % (CLOSURE_PATH, "deps.js")
    
    # The third party deps file uses paths relative to CLOSURE_PATH, so we
    # don't need a THIRD_PARTY_PATH.
    THIRD_PARTY_DEPS = ("../closure-library-read-only/third_party/closure/goog"
                        "/deps.js")
    
    APP_PATH = "src/"
    
    APP_DEPS_FILE = "deps/app_deps.js"
    
    CREATE_APP_DEPS_FILE = "%s %s %s%s" % ("python", DEPSWRITER,
                           "--root=src/ --output_file=", APP_DEPS_FILE)
    
    os.system(CREATE_APP_DEPS_FILE)
    
    # A map of namespaces to their filename.
    self.namespace_filenames = {}
    
    # A map of filenames to the namespaces they provide
    self.filenames_to_namespaces = {}
    
    # A map of namespaces to an array of the namespaces they require.
    self.n_dependency_map = {}
    
    # RegExp pattern that matches a goog.addDependency call to extract
    # the file name, provided and required namespaces.
    # goog.addDependency('goog\useragent\useragent.js',
    #                                     ['goog.userAgent'], ['goog.string']);
    pattern = re.compile(r"""^goog\.addDependency\(
                      (?P<filename>"\S*?\.js"),\ # Capture the filename
                      (?P<provided>\[.*?\]),\ # Capture the provided namespaces
                      (?P<required>\[.*?\]) # Capture the required namespaces
                      \);""", re.X)
    
    self.load_deps_file(CLOSURE_DEPS, CLOSURE_PATH, pattern)
    self.load_deps_file(THIRD_PARTY_DEPS, CLOSURE_PATH, pattern)
    self.load_deps_file(APP_DEPS_FILE, APP_PATH, pattern)
    
    os.remove('deps/app_deps.js')
    
    self.init_level = ModuleBuilder.InitLevel.N_DEPENDENCIES_MAPPED
  
  def get_n_dependency_list(self, namespaces, module):
    """Recursively map the nDependencies of a list of namespaces
    
    Helper method for `map_module_namespaces`.
    Given a list of namespaces, recursively traverse self.n_dependency_map
    and build an ordered list of all dependencies for each namespace in the
    module, starting from the top down.
    
    Args:
      namespaces: A list of namespaces whose dependencies we need to map
      module: The module object from self.modules
    """
    
    for namespace in namespaces:
      # Recurse all the way to the top of the tree, then begin adding things
      # from first to last, in order.
      n_deps = self.n_dependency_map[namespace]
      if len(n_deps) > 0:
        self.get_n_dependency_list(n_deps, module)
      
      module["n_dependency_list"].append(namespace)
      if namespace not in self.namespaces_to_module_map:
        self.namespaces_to_module_map[namespace] = []
        
      module_name = module["name"]
      if module_name not in self.namespaces_to_module_map[namespace]:
        self.namespaces_to_module_map[namespace].append(module_name)
  
  def map_module_namespaces(self):
    """Map the goog.* and app namespaces that belong in each module
    
    Read the namespaces array in each module object and recursively map out the
    full dependency tree for that module, including both user-defined and
    goog.* namespaces.
    
    Defines:
      self.namespaces_to_module_map: A map of namespaces to the modules in
          which they are required.
      self.modules[i]["n_dependency_list"]: A list in nDependency order for
          each module object.
    """
    
    if self.init_level != ModuleBuilder.InitLevel.N_DEPENDENCIES_MAPPED:
      self.map_namespace_dependencies()
    
    logging.info("Mapping namespaces to their modules...")
    
    # Maps namespaces to all modules in which they are used.
    self.namespaces_to_module_map = {}
    
    for module in self.modules:
      module["n_dependency_list"] = []
      self.get_n_dependency_list(module["namespaces"], module)
    
    self.init_level = ModuleBuilder.InitLevel.MODULE_NAMESPACES_MAPPED
  
  def find_closest_parent(self, target_modules):
    """Find the closest parent module to those given
    
    Find the module that is as close as possible to those given in the module
    dependency graph.  This is done in a few steps:
    
    1)  If only one module is passed in, that's the one.
    2)  If we've already computed this, return the result from
        self.module_parent_cache.
    3)  Determine if one of the given modules is a parent of all the others.
        If one of them is, return that one.
    4)  If all else fails, iterate through the entire self.modules array and
        find the one with the lowest aggregate 'level'.  In the example below,
        'settings' is one level below 'core'.  'core' has an aggregate level
        of 2 above ['settings', 'view'] and 3 above ['settings', 'upload'].
        Computing the parent modules for two non-interdependent modules is
        expensive, and a good argument for using a shallow module dependency
        graph.
    
    Example:
      core
      |--settings
      |--view
         |--upload
    
    Args:
      target_modules: A list of module names whose closest parent we're
          trying to find.
    
    Return:
      The name of the module in which this namespace should be included.
    """
    
    if len(target_modules) == 1:
      print "Only one module given: %s" % target_modules[0]
      return target_modules[0]
    
    # Check the cache and return it if we've already found the closest one.
    cache_key = ".".join(target_modules)
    if cache_key in self.module_parent_cache:
      # Cache value is stored as "module:level".
      # If it's already computed, we don't care about the level.
      print "Result already in the cache: %s" % (
        self.module_parent_cache[cache_key].split(":")[0])
      return self.module_parent_cache[cache_key].split(":")[0]
    
    # Remember,
    # self.modules[i]['m_dependents'] = {dependent_name: "xxx", level: x}
    
    # First, determine if one of the modules is a parent of all the others
    for target_module in target_modules:
      mod = self.modules_map[target_module]
      
      # Obviously, if a module has no dependencies, it can't be anyone's parent.
      if "m_dependents" in mod:
        m_dependents = [dep['dependent_name'] for dep in mod["m_dependents"]]
        
        is_parent = True
        for other_module in target_modules:
          if other_module != target_module:
            if other_module not in m_dependents:
              is_parent = False
              break
        
        if is_parent:
          print "%s is a parent of all other given modules" % target_module
          return target_module
    
    # If we got this far, none of the target modules is a parent for all the
    # others.  Find the nearest parent by iterating through all modules and
    # calculating the combined "levels" away from the target module nodes.
    
    # The closest we can possibly get is a combined "level" of
    # (1 x num_of_modules).  This is the case for sibling modules that all
    # extend from one parent module.
    min_level = len(target_modules)
    
    # Iterate through all of the modules.
    for module in self.modules:
      
      # Obviously we can skip any modules that don't have dependents
      if "m_dependents" in module:
        
        # Check that each target module is in this module's 'm_dependents' list
        all_found = True
        
        # Create a simple list of dependent names for easy iteration.
        m_dependents = [dep['dependent_name'] for dep in module["m_dependents"]]
        
        # Create a simple list of dependent levels for matching indexing into
        # both lists.
        m_dependents_levels = [dep['level'] for dep in module["m_dependents"]]
        
        level = 0
        for target_module in target_modules:
          if target_module not in m_dependents:
            all_found = False
            break
          else:
            level += m_dependents_levels[m_dependents.index(target_module)]
        
        if all_found:
          module_name = module["name"]
          print "%s is %d levels above the target modules" % (module_name, level)
          self.module_parent_cache[cache_key] = "%s:%d" % (module_name, level)
          if level == min_level:
            # If this module is a dependency for all target modules, and it is
            # at the minimum possible level, return it without looking for
            # other matches.
            print "%s is the min_level away from all modules" % module_name
            return module_name
          else:
            # If this is the first result, cache it.
            if cache_key not in self.module_parent_cache:
              self.module_parent_cache[cache_key] = ("%s:%d" %
                                                     (module_name, level))
            else:
              # Only store this result if it's fewer levels away than the
              # previous find.
              cached_level = self.module_parent_cache[cache_key].split(':')[1]
              if level < cached_level:
                self.module_parent_cache[cache_key] = ("%s:%d" %
                                                      (module_name, level))
    
    if cache_key not in self.module_parent_cache:
      raise Exception("No common parent module for modules: %s" %
                      ", ".join(target_modules))
    else:
      print "%s is the closest module to those given" % (
        self.module_parent_cache[cache_key].split(":")[0])
      return self.module_parent_cache[cache_key].split(":")[0]
  
  def analyze_dependencies_across_modules(self):
    """Determine what module each required namespace should be in.
    
    Analyze the m- and nDependency trees to determine what module each
    required namespace needs to be included with.  This is done by
    finding all modules that require each namespace and finding the
    closest parent module (think least common denominator) to ensure that code
    is not loaded until absolutely necessary.
    
    Defines:
      self.module_parent_cache: Results from finding the parent of multiple
          modules
    """
    
    # Since some files include namespaces that can be required separately
    # (for example goog.events and goog.events.EventType), keep track of the
    # filenames that have been included, not the namespaces themselves.
    included_files = []
    
    if self.init_level != ModuleBuilder.InitLevel.MODULE_NAMESPACES_MAPPED:
      self.map_namespace_dependencies()
    
    # Finding the closest parent module to a list of modules is very expensive
    # Cache results to avoid multiple look-ups.
    self.module_parent_cache = {}






    self.init_level = ModuleBuilder.InitLevel.DEPENDENCIES_PLACED

  def compile(self):
    """Calls the Closure Compiler with the necessary inputs to build the app."""
    
    # If we're not ready to compile, call the previous method in the sequence.
    if self.init_level != ModuleBuilder.InitLevel.DEPENDENCIES_PLACED:
      self.analyze_dependencies_across_modules()

    # Code to compile will go here once we're ready.

def main():
  logging.basicConfig(format=(sys.argv[0] + ': %(message)s'),
                      level=logging.INFO)
  
  logging.info("Initializing ModuleBuilder and preparing to compile...")

  builder = ModuleBuilder()
  builder.compile()
  
  print builder.find_closest_parent([u'deps', u'settings'])


if __name__ == "__main__":
  main()